package feiyanren.com;

public class A05_Demo5 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        int target = 5;
        int index = find(arr, target);
        System.out.println(index);
    }

    public static int find(int[] arr, int target) {
        int fibo_2 = 0;
        int fibo_1 = 1;
        int fibo = fibo_1 + fibo_2;
        while (fibo < arr.length) {
            fibo_2 = fibo_1;
            fibo_1 = fibo;
            fibo = fibo_1 + fibo_2;
        }
        int offset = -1;
        while (fibo_1 > 0) {
            //防止数组索引为负数；
            int i = Math.max(offset + fibo_2, 0);
            //防止数组索引越界；
            i = Math.min(i, arr.length - 1);
            if (arr[i] < target) {
                fibo = fibo_1;
                fibo_1 = fibo_2;
                fibo_2 = fibo - fibo_1;
                //重置偏移值;
                offset = i;
            } else if (arr[i] > target) {
                fibo = fibo_2;
                fibo_1 = fibo_1 - fibo_2;
                fibo_2 = fibo - fibo_1;
                //重置偏移值;
                offset = i;
            } else {
                return i;
            }
            //判断未判断的情况【数组个数为斐波那契数时会出现这种问题：最后一位没有进行判断】
            if (offset + 1 < arr.length && arr[offset + 1] == target) {
                return offset + 1;
            }
        }
        return -1;
    }
}
